package com.gin.soul.pojo.graph;

import com.alibaba.fastjson.JSONArray;
import com.gin.soul.pojo.EdgeEsEnterprisePersonBO;

import java.util.*;

public class GraphGenerator {

	// 股权穿透计算 graph.jpg
	public static void main(String[] args) {
		String listStr = "[{\"conProp\":\"50.0\",\"dst\":\"2210330005\",\"invType\":\"个人\",\"src\":\"2210310001\"},{\"conProp\":\"50.0\",\"dst\":\"2210310002\",\"invType\":\"企业\",\"src\":\"2210310001\"},{\"conProp\":\"50.0\",\"dst\":\"2210310003\",\"invType\":\"企业\",\"src\":\"2210310002\"},{\"conProp\":\"50.0\",\"dst\":\"2210330004\",\"invType\":\"个人\",\"src\":\"2210310002\"},{\"conProp\":\"50.0\",\"dst\":\"2210310004\",\"invType\":\"企业\",\"src\":\"2210310003\"},{\"conProp\":\"25.0\",\"dst\":\"2210330003\",\"invType\":\"个人\",\"src\":\"2210310003\"},{\"conProp\":\"25.0\",\"dst\":\"2210330005\",\"invType\":\"个人\",\"src\":\"2210310003\"},{\"conProp\":\"50.0\",\"dst\":\"2210330001\",\"invType\":\"个人\",\"src\":\"2210310004\"},{\"conProp\":\"50.0\",\"dst\":\"2210330002\",\"invType\":\"个人\",\"src\":\"2210310004\"}]";
		List<EdgeEsEnterprisePersonBO> edgeList = JSONArray.parseArray(listStr, EdgeEsEnterprisePersonBO.class);
		System.out.println(edgeList);

		Graph graph = createGraph(edgeList, "2210310001");
		bfs2(graph.nodes.get("2210310001"));
	}

	public static Graph createGraph(List<EdgeEsEnterprisePersonBO> edgeList, String root) {
		Graph graph = new Graph(edgeList);
		for (EdgeEsEnterprisePersonBO edge : edgeList) {
			// 拿到每一条边
			double weight = Double.parseDouble(edge.getConProp());
			String from = edge.getSrc();
			String to = edge.getDst();
			if (!graph.nodes.containsKey(from)) {
				graph.nodes.put(from, new Node(from));
			}
			if (!graph.nodes.containsKey(to)) {
				graph.nodes.put(to, new Node(to));
			}
			Node fromNode = graph.nodes.get(from);
			Node toNode = graph.nodes.get(to);
			Edge newEdge = new Edge(weight, edge.getInvType(), fromNode, toNode);
			if ("个人".equals(edge.getInvType())) {
				fromNode.nexts.addFirst(toNode);
			} else {
				fromNode.nexts.addLast(toNode);
			}

			fromNode.out++;
			toNode.in++;
			fromNode.edges.put(toNode.value, newEdge);
		}
		return graph;
	}

	// 从node出发，进行宽度优先遍历
	public static void bfs2(Node node) {
		if (node == null) {
			return;
		}
		Queue<Node> queue = new LinkedList<>();
		//图需要set去重,避免出现环情况下,循环遍历(二叉树没有环, 所以二叉树宽度优先没有set)
		HashSet<Node> set = new HashSet<>();
		queue.add(node);
		set.add(node);
		double tmp = 1.0D;
		while (!queue.isEmpty()) {
			//弹出则打印
			Node cur = queue.poll();
			System.out.println(cur.value);
			//所有直接邻居,不存在set中的就放入队列中
			for (Node next : cur.nexts) {
				if (!set.contains(next)) {
					queue.add(next);
					Edge edge = cur.edges.get(next.value);
					if ("个人".equals(edge.invType)) {
						System.out.println(next.value + " " + (tmp * edge.weight / 100));
					} else {
						set.add(next);
						tmp = tmp * edge.weight / 100;
					}
				}
			}
		}
	}

	// 从node出发，进行宽度优先遍历
	public static void bfs(Node node) {
		if (node == null) {
			return;
		}
		Queue<Node> queue = new LinkedList<>();
		//图需要set去重,避免出现环情况下,循环遍历(二叉树没有环, 所以二叉树宽度优先没有set)
		HashSet<Node> set = new HashSet<>();
		queue.add(node);
		set.add(node);
		while (!queue.isEmpty()) {
			//弹出则打印
			Node cur = queue.poll();
			System.out.println(cur.value);
			//所有直接邻居,不存在set中的就放入队列中
			for (Node next : cur.nexts) {
				if (!set.contains(next)) {
					set.add(next);
					queue.add(next);
				}
			}
		}
	}

	//深度优先遍历
	public static void dfs(Node node) {
		if (node == null) {
			return;
		}
		//栈, 实际记录的是深度遍历的路径
		Stack<Node> stack = new Stack<>();
		//保证不重复进入
		HashSet<Node> set = new HashSet<>();
		//先压入深度遍历的出发点
		stack.add(node);
		set.add(node);
		System.out.println(node.value);
		while (!stack.isEmpty()) {
			//弹出节点, 并获取节点是否具有下个节点
			Node cur = stack.pop();
			for (Node next : cur.nexts) {
				//判断下个节点是否已经走过
				if (!set.contains(next)) {
					//没有走过则把当前节点和下个节点逐步压入
					//即:栈中保留了整条从开始节点出发的深度路径
					stack.push(cur);
					stack.push(next);
					set.add(next);
					System.out.println(next.value);
					//不再寻找宽度的next, 而是跳出, 去找next的next了
					//宽度的next可以在一条深度走到路的尽头后, 通过栈弹出进行回退深度, 然后在while继续遍历宽度
					break;
				}
			}
		}
	}

}
